

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;auto&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon%2032x32.ico">
  <link rel="icon" href="/img/favicon%2032x32.ico">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
    <meta http-equiv="Content-Security-Policy" content="upgrade-insecure-requests">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="hypocrite30">
  <meta name="keywords" content="">
  
  <title>Java常用集合源码分析 Ⅱ - hypocrite30</title>

  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.3/dist/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/github-markdown-css@4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@10.4.0/styles/idea.min.css" />
    
  

  
    <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css" />
  



<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_kmeydafke9r.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    var CONFIG = {"hostname":"hypocrite30.gitee.io","root":"/","version":"1.8.9","typing":{"enable":true,"typeSpeed":70,"cursorChar":"_","loop":false},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"right","visible":"hover","icon":"§"},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"copy_btn":true,"image_zoom":{"enable":true},"toc":{"enable":true,"headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":2},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":false,"offset_factor":2},"web_analytics":{"enable":false,"baidu":"b5f391eebc7eaea88e68a49d5924e381","google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null}}};
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.3.0"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>Hypocrite30 BLOG</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/links/">
                <i class="iconfont icon-link-fill"></i>
                友链
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner" id="banner" parallax=true
         style="background: url('/img/postPage.jpg') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="page-header text-center fade-in-up">
            <span class="h2" id="subtitle" title="Java常用集合源码分析 Ⅱ">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2021-08-16 21:30" pubdate>
        2021年8月16日 晚上
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      7.4k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      128
       分钟
    </span>
  

  
  
    
      <!-- 不蒜子统计文章PV -->
      <span id="busuanzi_container_page_pv" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="busuanzi_value_page_pv"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto">
            <!-- SEO header -->
            <h1 style="display: none">Java常用集合源码分析 Ⅱ</h1>
            
              <p class="note note-info">
                
                  本文最后更新于：2021年10月17日 晚上
                
              </p>
            
            <div class="markdown-body">
              <h1 id="Java常用集合源码分析-Ⅱ"><a href="#Java常用集合源码分析-Ⅱ" class="headerlink" title="Java常用集合源码分析 Ⅱ"></a>Java常用集合源码分析 Ⅱ</h1><blockquote>
<p>@Version: JDK 1.8</p>
<p>@IDE: IntellJ IDEA 2021.1</p>
<p>@Date: 2021/8/10</p>
<p>@Author: Hypocrite30</p>
</blockquote>
<h2 id="一、集合"><a href="#一、集合" class="headerlink" title="一、集合"></a>一、集合</h2><h3 id="Ⅰ、Set接口"><a href="#Ⅰ、Set接口" class="headerlink" title="Ⅰ、Set接口"></a>Ⅰ、Set接口</h3><ul>
<li>无序「添加和取出的顺序不一致」，没有索引</li>
<li>不允许<strong>重复元素</strong>，所以最多包含一个 <code>null</code></li>
<li>常用实现类有 <code>HashSet</code> &amp; <code>TreeSet</code></li>
</ul>
<h3 id="Ⅱ、Map接口"><a href="#Ⅱ、Map接口" class="headerlink" title="Ⅱ、Map接口"></a>Ⅱ、Map接口</h3><ul>
<li><code>Map</code> 与 <code>Collection</code> 并列存在。用于保存具有<strong>映射关系</strong>的数据：<strong>Key-Value</strong></li>
<li><code>Map</code> 中的 <code>key</code> 和 <code>value</code> 可以是任何引用类型的数据，会封装到 <code>HashMap$Node</code> 对象中</li>
<li><code>Map</code> 中的 <code>key</code> 不允许重复，原因和 <code>HashSet</code> 一样，<code>Map</code> 中的 <code>value</code> 可以重复</li>
<li><code>Map</code> 的 <code>key </code>可以为 <code>null</code> , <code>value</code> 也可以为 <code>null</code>，注意 <code>key</code>为 <code>null</code>, 只能有<strong>一个</strong>，<code>value</code> 为 <code>null</code> ，可以多个.</li>
<li>常用 <code>String</code> 类作为 <code>Map</code> 的 <code>key</code></li>
<li><code>key</code> 和 <code>value</code> 之间存在<strong>单向一对一</strong>关系，即通过指定的 <code>key</code> 总能找到对应的 <code>value</code></li>
</ul>
<h2 id="二、HashMap"><a href="#二、HashMap" class="headerlink" title="二、HashMap"></a>二、HashMap</h2><h3 id="Ⅰ、Field"><a href="#Ⅰ、Field" class="headerlink" title="Ⅰ、Field"></a>Ⅰ、Field</h3><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// 默认初始化容量，且容量必须是 2 次幂</span><br><span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> DEFAULT_INITIAL_CAPACITY = <span class="hljs-number">1</span> &lt;&lt; <span class="hljs-number">4</span>; <span class="hljs-comment">// aka 16</span><br><span class="hljs-comment">// 最大容量，在两个带参构造中的任何一个隐式指定更高的值时使用。</span><br><span class="hljs-comment">// 必须是 2 的次幂 &lt;= 1&lt;&lt;30</span><br><span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> MAXIMUM_CAPACITY = <span class="hljs-number">1</span> &lt;&lt; <span class="hljs-number">30</span>;<br><span class="hljs-comment">// 默认缺省负载因子大小</span><br><span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">float</span> DEFAULT_LOAD_FACTOR = <span class="hljs-number">0.75f</span>;<br><span class="hljs-comment">// 桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 &gt; 该值时，则将链表转换成红黑树</span><br><span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> TREEIFY_THRESHOLD = <span class="hljs-number">8</span>;<br><span class="hljs-comment">// 桶的链表还原阈值</span><br><span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> UNTREEIFY_THRESHOLD = <span class="hljs-number">6</span>;<br><span class="hljs-comment">// 存储箱可树化的最小表容量</span><br><span class="hljs-comment">// 当Map table 数组数量「桶数量」超过这个值时，表中的桶才能进行树形化,</span><br><span class="hljs-comment">// 否则桶内元素太多时会对数组扩容，而不是树形化 </span><br><span class="hljs-comment">// 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD</span><br><span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> MIN_TREEIFY_CAPACITY = <span class="hljs-number">64</span>;<br><span class="hljs-comment">// 哈希表，即 Node 数组</span><br><span class="hljs-keyword">transient</span> Node&lt;K,V&gt;[] table;<br><span class="hljs-comment">// Set集合，存 Node 节点，因为 Node implements Entry，多态的形式</span><br><span class="hljs-keyword">transient</span> Set&lt;Map.Entry&lt;K,V&gt;&gt; entrySet;<br><span class="hljs-comment">// 哈希表元素个数</span><br><span class="hljs-keyword">transient</span> <span class="hljs-keyword">int</span> size;<br><span class="hljs-comment">// 哈希表修改次数，不包括 K-V 的替换</span><br><span class="hljs-keyword">transient</span> <span class="hljs-keyword">int</span> modCount;<br><span class="hljs-comment">// 要调整大小的下一个大小值，为「容量 * 负载系数」</span><br><span class="hljs-keyword">int</span> threshold;<br><span class="hljs-comment">// 负载因子，建议用默认的 0.75</span><br><span class="hljs-keyword">final</span> <span class="hljs-keyword">float</span> loadFactor;<br></code></pre></div></td></tr></table></figure>


<h3 id="Ⅱ、Constructor"><a href="#Ⅱ、Constructor" class="headerlink" title="Ⅱ、Constructor"></a>Ⅱ、Constructor</h3><h4 id="无参构造"><a href="#无参构造" class="headerlink" title="无参构造"></a>无参构造</h4><ul>
<li>使用默认的 负载因子，容量还是有其它的初始化设置都是默认的</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">HashMap</span><span class="hljs-params">()</span> </span>&#123;<br>    <span class="hljs-keyword">this</span>.loadFactor = DEFAULT_LOAD_FACTOR; <span class="hljs-comment">// all other fields defaulted</span><br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="有参构造"><a href="#有参构造" class="headerlink" title="有参构造"></a>有参构造</h4><ol>
<li>自定义 <code>table</code> 容量，负载因子是默认的 <code>0.75</code></li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">HashMap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity)</span> </span>&#123;<br>    <span class="hljs-keyword">this</span>(initialCapacity, DEFAULT_LOAD_FACTOR);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ol start="2">
<li>自定义 容量 和 负载因子</li>
</ol>
<ul>
<li>检验 <strong>容量</strong> 的合法性，不合法抛异常</li>
<li><strong>if</strong> 自定义容量超过限制最大值 <code>1 &lt;&lt; 30</code>，容量按最大值来取</li>
<li>检验 <strong>负载因子</strong> 是否「小于0 || 不是一个数」，不合法抛异常</li>
<li>阈值 <code>threshold</code> 「要调整大小的下一个大小值」需要 「计算大于等于给定数的最近2次幂数」，因为阈值必须是 2 次幂的数。</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">HashMap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity, <span class="hljs-keyword">float</span> loadFactor)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (initialCapacity &lt; <span class="hljs-number">0</span>)<br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException(<span class="hljs-string">&quot;Illegal initial capacity: &quot;</span> +<br>                                           initialCapacity);<br>    <span class="hljs-comment">// MAXIMUM_CAPACITY = 1 &lt;&lt; 30;</span><br>    <span class="hljs-keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)<br>        initialCapacity = MAXIMUM_CAPACITY;<br>    <span class="hljs-keyword">if</span> (loadFactor &lt;= <span class="hljs-number">0</span> || Float.isNaN(loadFactor))<br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException(<span class="hljs-string">&quot;Illegal load factor: &quot;</span> +<br>                                           loadFactor);<br>    <span class="hljs-keyword">this</span>.loadFactor = loadFactor;<br>    <span class="hljs-keyword">this</span>.threshold = tableSizeFor(initialCapacity);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<p>📌：按照逻辑 (<strong>当size到达threshold时扩容</strong>) <code>threshold</code> 应该这样写 「<code>this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;</code>」但 jdk8 之后的构造方法，没有对 <code>table</code> 数组进行初始化，而是推移到 <code>HashMap::put</code>，在 <code>put</code> 中对 <code>threshold</code> 重新计算。</p>
<ol start="3">
<li>传入 <code>Map</code>，使用默认 负载因子，容量足够存下入参的 <code>Map</code></li>
</ol>
<ul>
<li>负载因子使用默认 <strong>0.75</strong></li>
<li>然后创建table，将入参 map 值存入： <code>putMapEntries</code>，<code>boolean evict = false</code> 说明是表创建模式</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">HashMap</span><span class="hljs-params">(Map&lt;? extends K, ? extends V&gt; m)</span> </span>&#123;<br>    <span class="hljs-keyword">this</span>.loadFactor = DEFAULT_LOAD_FACTOR;<br>    putMapEntries(m, <span class="hljs-keyword">false</span>);<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h3 id="Ⅲ、Method"><a href="#Ⅲ、Method" class="headerlink" title="Ⅲ、Method"></a>Ⅲ、Method</h3><h4 id="插入元素-put-K-key-V-value"><a href="#插入元素-put-K-key-V-value" class="headerlink" title="插入元素 put(K key, V value)"></a>插入元素 put(K key, V value)</h4><ul>
<li>实际的实现函数是 <code>putVal(...)</code></li>
<li><code>putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)</code><ul>
<li>哈希值需要重新计算，使用 <code>hash()</code> 再次计算哈希值，使得哈希值更分散</li>
<li><code>onlyIfAbsent = false</code>：遇到相同的 <code>key</code>，则会替换原先的值，并返回旧值，否则返回 <code>null</code></li>
<li><code>evict = true</code>：不是创建模式</li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">put</span><span class="hljs-params">(K key, V value)</span> </span>&#123;<br>    <span class="hljs-keyword">return</span> putVal(hash(key), key, value, <span class="hljs-keyword">false</span>, <span class="hljs-keyword">true</span>);<br>&#125;<br></code></pre></div></td></tr></table></figure>




<h4 id="Map-put-实现方法及相关方法-putVal-…"><a href="#Map-put-实现方法及相关方法-putVal-…" class="headerlink" title="Map.put 实现方法及相关方法 putVal(…)"></a>Map.put 实现方法及相关方法 putVal(…)</h4><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">/**</span><br><span class="hljs-comment">  * 实现 Map.put 和 相关方法</span><br><span class="hljs-comment">  * <span class="hljs-doctag">@param</span> hash key的哈希值</span><br><span class="hljs-comment">  * <span class="hljs-doctag">@param</span> key key</span><br><span class="hljs-comment">  * <span class="hljs-doctag">@param</span> value value</span><br><span class="hljs-comment">  * <span class="hljs-doctag">@param</span> onlyIfAbsent true: 不替换已存在元素; false: 替换</span><br><span class="hljs-comment">  * <span class="hljs-doctag">@param</span> evict false: 表为创建模式</span><br><span class="hljs-comment">  * <span class="hljs-doctag">@return</span> 以前的值，如果没有，则为 null</span><br><span class="hljs-comment">  */</span><br><span class="hljs-function"><span class="hljs-keyword">final</span> V <span class="hljs-title">putVal</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, K key, V value, <span class="hljs-keyword">boolean</span> onlyIfAbsent,</span></span><br><span class="hljs-function"><span class="hljs-params">               <span class="hljs-keyword">boolean</span> evict)</span> </span>&#123;<br>    <span class="hljs-comment">/**</span><br><span class="hljs-comment">      * tab: 桶数组</span><br><span class="hljs-comment">      * p: 当前的桶</span><br><span class="hljs-comment">      * n: 桶数组长度</span><br><span class="hljs-comment">      * i: 路由地址「下标位置」</span><br><span class="hljs-comment">      */</span><br>    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; <span class="hljs-keyword">int</span> n, i;<br>    <span class="hljs-comment">// 如果 table 没初始化或长度为0，则扩容</span><br>    <span class="hljs-keyword">if</span> ((tab = table) == <span class="hljs-keyword">null</span> || (n = tab.length) == <span class="hljs-number">0</span>)<br>        n = (tab = resize()).length;<br>    <span class="hljs-comment">// 如果 hash 位置桶没有数据，则直接插入数据</span><br>    <span class="hljs-comment">// (length - 1) &amp; hash == hash % length</span><br>    <span class="hljs-keyword">if</span> ((p = tab[i = (n - <span class="hljs-number">1</span>) &amp; hash]) == <span class="hljs-keyword">null</span>)<br>        tab[i] = newNode(hash, key, value, <span class="hljs-keyword">null</span>);<br>    <span class="hljs-comment">// 如果桶有数据，再放入桶中</span><br>    <span class="hljs-keyword">else</span> &#123;<br>        <span class="hljs-comment">// e: 临时的 Node; k: 临时的 key</span><br>        Node&lt;K,V&gt; e; K k;<br>        <span class="hljs-comment">// 判断put的元素和已经存在的元素是相同(hash一致，并且equals返回true)</span><br>        <span class="hljs-comment">// 则将已存在的节点暂存</span><br>        <span class="hljs-keyword">if</span> (p.hash == hash &amp;&amp;<br>            ((k = p.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))<br>            e = p;<br>        <span class="hljs-comment">// put的元素与已存在元素不同</span><br>        <span class="hljs-comment">// 如果桶内类型时树结构，则插入到树中</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (p <span class="hljs-keyword">instanceof</span> TreeNode)<br>            e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(<span class="hljs-keyword">this</span>, tab, hash, key, value);<br>        <span class="hljs-comment">// 不是树结构，则插入到链表中</span><br>        <span class="hljs-keyword">else</span> &#123;<br>            <span class="hljs-comment">// 遍历到链表结尾插入</span><br>            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> binCount = <span class="hljs-number">0</span>; ; ++binCount) &#123;<br>                <span class="hljs-keyword">if</span> ((e = p.next) == <span class="hljs-keyword">null</span>) &#123;<br>                    p.next = newNode(hash, key, value, <span class="hljs-keyword">null</span>);<br>                    <span class="hljs-comment">// 如果链表长度大于阈值，则转化为树结构</span><br>                    <span class="hljs-keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="hljs-number">1</span>) <span class="hljs-comment">// -1 for 1st</span><br>                        treeifyBin(tab, hash);<br>                    <span class="hljs-keyword">break</span>;<br>                &#125;<br>                <span class="hljs-comment">// 如果已经存在key，停止遍历，进行下面的替换操作</span><br>                <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp;<br>                    ((k = e.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))<br>                    <span class="hljs-keyword">break</span>;<br>                <span class="hljs-comment">// 游标向后移动</span><br>                p = e;<br>            &#125;<br>        &#125;<br>        <span class="hljs-comment">// 判断 K-V 有没有插入进哈希表里</span><br>        <span class="hljs-comment">// 上面操作，只要插入进桶里，e != null，否则还是初始的 null 值</span><br>        <span class="hljs-keyword">if</span> (e != <span class="hljs-keyword">null</span>) &#123; <span class="hljs-comment">// existing mapping for key</span><br>            V oldValue = e.value;<br>            <span class="hljs-comment">// onlyIfAbsent = true: 不替换旧值</span><br>            <span class="hljs-keyword">if</span> (!onlyIfAbsent || oldValue == <span class="hljs-keyword">null</span>)<br>                e.value = value;<br>            afterNodeAccess(e);<br>            <span class="hljs-keyword">return</span> oldValue;<br>        &#125;<br>    &#125;<br>    ++modCount;<br>    <span class="hljs-comment">// K-V 超过阈值，扩容</span><br>    <span class="hljs-keyword">if</span> (++size &gt; threshold)<br>        resize();<br>    afterNodeInsertion(evict);<br>    <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/Map.put.png" srcset="/img/loading.gif" lazyload alt="HashMap.putVal"></p>
<h4 id="Map-putAll-实现方法及Map构造方法-putMapEntries-…"><a href="#Map-putAll-实现方法及Map构造方法-putMapEntries-…" class="headerlink" title="Map.putAll 实现方法及Map构造方法 putMapEntries(…)"></a>Map.putAll 实现方法及Map构造方法 putMapEntries(…)</h4><ul>
<li><p><code>((float)s / loadFactor) + 1.0F</code> 加 1 的目的：计算得到容量有可能为小数，后面需要对长度进行取整，容量就会算小，所以加一取整，就是向上取整。</p>
</li>
<li><p><code>if (t &gt; threshold)</code>，此 <code>threshold</code> 存放的是 <code>capacity</code> 的值。在 table 未初始化时，带初始化容量的构造器会传入 <code>capacity</code>，并通过 <code>tableSizeFor</code> 计算扩容阈值，让 <code>threshold</code> 暂存这个值。在 <code>HashMap</code> 中没有<code>capacity</code> 这个变量，只是作为 table 数组的大小而隐式存在。</p>
</li>
<li><p><code>else if (s &gt; threshold)</code> 说明入参 map 的 <code>size</code> 已经大于当前 <code>map</code> 的 <code>threshold</code>，即当前 <code>map</code> 肯定装不下两个 map 的并集，所以需要扩容</p>
</li>
<li><p><code>putVal</code> 过程中也可能出现扩容</p>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">final</span> <span class="hljs-keyword">void</span> <span class="hljs-title">putMapEntries</span><span class="hljs-params">(Map&lt;? extends K, ? extends V&gt; m, <span class="hljs-keyword">boolean</span> evict)</span> </span>&#123;<br>    <span class="hljs-comment">// 入参集合长度</span><br>    <span class="hljs-keyword">int</span> s = m.size();<br>    <span class="hljs-keyword">if</span> (s &gt; <span class="hljs-number">0</span>) &#123;<br>        <span class="hljs-comment">// table 没有被初始化</span><br>        <span class="hljs-keyword">if</span> (table == <span class="hljs-keyword">null</span>) &#123; <span class="hljs-comment">// pre-size</span><br>            <span class="hljs-comment">// s/loadFactor 计算入参map长度是否达到扩容阈值</span><br>            <span class="hljs-keyword">float</span> ft = ((<span class="hljs-keyword">float</span>)s / loadFactor) + <span class="hljs-number">1.0F</span>;<br>            <span class="hljs-comment">// 入参map长度是否超过最大容量，否则取整</span><br>            <span class="hljs-keyword">int</span> t = ((ft &lt; (<span class="hljs-keyword">float</span>)MAXIMUM_CAPACITY) ?<br>                     (<span class="hljs-keyword">int</span>)ft : MAXIMUM_CAPACITY);<br>            <span class="hljs-comment">// 如果计算出来的容量t &gt; 当前暂存容量，会用t计算出新扩容阈值</span><br>            <span class="hljs-keyword">if</span> (t &gt; threshold)<br>                threshold = tableSizeFor(t);<br>        &#125;<br>        <span class="hljs-comment">// table 已经初始化，且 m 元素个数大于阈值，扩容处理</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (s &gt; threshold)<br>            resize();<br>        <span class="hljs-comment">// 将 m 中所有元素添加到 table 中</span><br>        <span class="hljs-keyword">for</span> (Map.Entry&lt;? extends K, ? extends V&gt; e : m.entrySet()) &#123;<br>            K key = e.getKey();<br>            V value = e.getValue();<br>            putVal(hash(key), key, value, <span class="hljs-keyword">false</span>, evict);<br>        &#125;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>




<h4 id="扩容方法-resize"><a href="#扩容方法-resize" class="headerlink" title="扩容方法 resize()"></a>扩容方法 resize()</h4><ul>
<li>注释①：<code>public HashMap(int initialCapacity, float loadFactor)</code> 两个参数的构造方法，会使用 <code>tableSizeFor()</code> 获得大于等于初始容量的最近2次幂数，并给 <code>threshold</code> 赋值，导致在 <code>else if (oldThr &gt; 0)</code> 判断时成立，有参构造都会直接或间接使用到 <code>tableSizeFor</code>，所以都会走这段程序</li>
<li>注释②：<code>if (newThr == 0)</code> 的情况，有两种。<ul>
<li>一、在上面 <code>else if ((newCap = oldCap &lt;&lt; 1) &lt; MAXIMUM_CAPACITY &amp;&amp; oldCap &gt;= DEFAULT_INITIAL_CAPACITY)</code> 的判断，如果<strong>不满足</strong> <code>oldCap &gt;= DEFAULT_INITIAL_CAPACITY(16)</code>，即传入的初始化容量小于 16，则没法完成 <code>newThr</code> 的赋值，则 <code>newThr == 0</code>  </li>
<li>二、<code>else if (oldThr &gt; 0)</code> 中，也没有对 <code>newThr</code> 进行赋值，所以此时也是 <code>newThr == 0</code></li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">final</span> Node&lt;K,V&gt;[] resize() &#123;<br>    <span class="hljs-comment">// 旧哈希表</span><br>    Node&lt;K,V&gt;[] oldTab = table;<br>    <span class="hljs-comment">// 旧table数组长度</span><br>    <span class="hljs-keyword">int</span> oldCap = (oldTab == <span class="hljs-keyword">null</span>) ? <span class="hljs-number">0</span> : oldTab.length;<br>    <span class="hljs-comment">// 扩容之前的扩容阈值，触发本次扩容</span><br>    <span class="hljs-keyword">int</span> oldThr = threshold;<br>    <span class="hljs-comment">// newCap: 扩容之后的容量大小</span><br>    <span class="hljs-comment">// newThr: 扩容之后，下次扩容的触发条件</span><br>    <span class="hljs-keyword">int</span> newCap, newThr = <span class="hljs-number">0</span>;<br>    <br>    <span class="hljs-comment">// 哈希表已经初始化过了，正常扩容</span><br>    <span class="hljs-keyword">if</span> (oldCap &gt; <span class="hljs-number">0</span>) &#123;<br>        <span class="hljs-comment">// 旧容量超出最大容量，则不扩容，阈值保持为int最大值，返回旧表</span><br>        <span class="hljs-keyword">if</span> (oldCap &gt;= MAXIMUM_CAPACITY) &#123;<br>            threshold = Integer.MAX_VALUE;<br>            <span class="hljs-keyword">return</span> oldTab;<br>        &#125;<br>        <span class="hljs-comment">// 新容量为旧容量扩大一倍，且小于最大容量</span><br>        <span class="hljs-comment">// 还要满足：旧容量 &lt;= 16，才将新扩容阈值扩大一倍</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((newCap = oldCap &lt;&lt; <span class="hljs-number">1</span>) &lt; MAXIMUM_CAPACITY &amp;&amp;<br>                 oldCap &gt;= DEFAULT_INITIAL_CAPACITY)<br>            newThr = oldThr &lt;&lt; <span class="hljs-number">1</span>; <span class="hljs-comment">// double threshold</span><br>    &#125;<br>    <span class="hljs-comment">// 下面都是未初始化情况</span><br>    <span class="hljs-comment">// 注释①</span><br>    <span class="hljs-comment">// 未初始化，oldThr旧扩容阈值已经计算的情况是有参构造中计算的</span><br>    <span class="hljs-comment">// 1. public HashMap(int initialCapacity, float loadFactor)</span><br>    <span class="hljs-comment">// 2. public HashMap(int initialCapacity</span><br>    <span class="hljs-comment">// 3. public HashMap(Map&lt;? extends K, ? extends V&gt; m)</span><br>    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (oldThr &gt; <span class="hljs-number">0</span>) <span class="hljs-comment">// 初始容量设置为阈值，容量为2的次幂</span><br>        newCap = oldThr;<br>    <span class="hljs-comment">// 1. oldThr == 0 -&gt; 无参构造创建的table</span><br>    <span class="hljs-comment">// 2. oldCap == 0 -&gt; 因为容量最小为0，不为负数</span><br>    <span class="hljs-keyword">else</span> &#123;               <span class="hljs-comment">// 零初始阈值表示使用默认值</span><br>        newCap = DEFAULT_INITIAL_CAPACITY; <span class="hljs-comment">// 16</span><br>        newThr = (<span class="hljs-keyword">int</span>)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); <span class="hljs-comment">// 16 * 0.75 = 12</span><br>    &#125;<br>    <br>    <span class="hljs-comment">// 注释②</span><br>    <span class="hljs-comment">// newThr == 0时，通过 newCap * loadFactor 计算 newThr，即新的扩容上限</span><br>    <span class="hljs-keyword">if</span> (newThr == <span class="hljs-number">0</span>) &#123;<br>        <span class="hljs-keyword">float</span> ft = (<span class="hljs-keyword">float</span>)newCap * loadFactor;<br>        newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (<span class="hljs-keyword">float</span>)MAXIMUM_CAPACITY ?<br>                  (<span class="hljs-keyword">int</span>)ft : Integer.MAX_VALUE);<br>    &#125;<br>    <span class="hljs-comment">// 更新 threshold，下次按照本次计算的结果作为扩容上限</span><br>    threshold = newThr;<br>    <span class="hljs-comment">// 以上做了两件事：计算 newCap &amp; newThr</span><br>    <span class="hljs-comment">// 以下完成扩容操作</span><br>    <span class="hljs-meta">@SuppressWarnings(&#123;&quot;rawtypes&quot;,&quot;unchecked&quot;&#125;)</span><br>    <span class="hljs-comment">// 创建新数组，并赋值替换原table，在一开始就将原table 用 oldTab 标记出来</span><br>    Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])<span class="hljs-keyword">new</span> Node[newCap];<br>    table = newTab;<br>    <span class="hljs-comment">// 扩容前，table不为null</span><br>    <span class="hljs-keyword">if</span> (oldTab != <span class="hljs-keyword">null</span>) &#123;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; oldCap; ++j) &#123;<br>            <span class="hljs-comment">// 当前 node 节点</span><br>            Node&lt;K,V&gt; e;<br>            <span class="hljs-comment">// 说明当前节点有数据，但数据结构并不清楚</span><br>            <span class="hljs-keyword">if</span> ((e = oldTab[j]) != <span class="hljs-keyword">null</span>) &#123;<br>                <span class="hljs-comment">// help GC</span><br>                oldTab[j] = <span class="hljs-keyword">null</span>;<br>                <span class="hljs-comment">// next无值，没有发生碰撞，直接存入新桶中</span><br>                <span class="hljs-comment">// 寻址算法：(length - 1) &amp; hash == hash % length，其实length为2次幂数</span><br>                <span class="hljs-keyword">if</span> (e.next == <span class="hljs-keyword">null</span>)<br>                    newTab[e.hash &amp; (newCap - <span class="hljs-number">1</span>)] = e;<br>                <span class="hljs-comment">// 树结构</span><br>                <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (e <span class="hljs-keyword">instanceof</span> TreeNode)<br>                    ((TreeNode&lt;K,V&gt;)e).split(<span class="hljs-keyword">this</span>, newTab, j, oldCap);<br>                <span class="hljs-comment">// 链表结构</span><br>                <span class="hljs-keyword">else</span> &#123; <span class="hljs-comment">// preserve order</span><br>                    <span class="hljs-comment">// 低位链表:存放在扩容之后的数组的下标位置，与当前数组的下标位置一致</span><br>                    Node&lt;K,V&gt; loHead = <span class="hljs-keyword">null</span>, loTail = <span class="hljs-keyword">null</span>;<br>                    <span class="hljs-comment">// 高位链表:存放在扩容之后的数组的下标位置，为当前数组下标位置+扩容之前数组的长度</span><br>                    Node&lt;K,V&gt; hiHead = <span class="hljs-keyword">null</span>, hiTail = <span class="hljs-keyword">null</span>;<br>                    <span class="hljs-comment">// 当前节点的下个元素</span><br>                    Node&lt;K,V&gt; next;<br>                    <span class="hljs-keyword">do</span> &#123;<br>                        next = e.next;<br>                        <span class="hljs-comment">/**</span><br><span class="hljs-comment">                          * hash: .... 1 1111</span><br><span class="hljs-comment">                          * hash: .... 0 1111</span><br><span class="hljs-comment">                          * oldCap: ...1 0000</span><br><span class="hljs-comment">                          * if 走低位，else 走高位</span><br><span class="hljs-comment">                          */</span><br>                        <span class="hljs-keyword">if</span> ((e.hash &amp; oldCap) == <span class="hljs-number">0</span>) &#123;<br>                            <span class="hljs-keyword">if</span> (loTail == <span class="hljs-keyword">null</span>)<br>                                loHead = e;<br>                            <span class="hljs-keyword">else</span><br>                                loTail.next = e;<br>                            loTail = e;<br>                        &#125;<br>                        <span class="hljs-comment">// 新table的位置在高位「原索引+旧容量」</span><br>                        <span class="hljs-keyword">else</span> &#123;<br>                            <span class="hljs-keyword">if</span> (hiTail == <span class="hljs-keyword">null</span>)<br>                                hiHead = e;<br>                            <span class="hljs-keyword">else</span><br>                                hiTail.next = e;<br>                            hiTail = e;<br>                        &#125;<br>                    &#125; <span class="hljs-keyword">while</span> ((e = next) != <span class="hljs-keyword">null</span>);<br>                    <span class="hljs-comment">// 原索引放到新桶里面</span><br>                    <span class="hljs-keyword">if</span> (loTail != <span class="hljs-keyword">null</span>) &#123;<br>                        loTail.next = <span class="hljs-keyword">null</span>;<br>                        newTab[j] = loHead;<br>                    &#125;<br>                    <span class="hljs-comment">// 原索引 + oldCap 放到新桶里</span><br>                    <span class="hljs-keyword">if</span> (hiTail != <span class="hljs-keyword">null</span>) &#123;<br>                        hiTail.next = <span class="hljs-keyword">null</span>;<br>                        newTab[j + oldCap] = hiHead;<br>                    &#125;<br>                &#125;<br>            &#125;<br>        &#125;<br>    &#125;<br>    <span class="hljs-keyword">return</span> newTab;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<p>📌补充：</p>
<ol>
<li>当HashMap中的其中一个链表的对象个数如果达到了 8 个，此时如果数组长度没有达到 64，那么HashMap 会先扩容解决，如果已经达到了 64，那么这个链表会变成红黑树，节点类型由 Node 变成TreeNode 类型。当然，如果映射关系被移除后，下次执行resize方法时判断树的节点个数低于 6，也会再把树转换为链表。</li>
<li>HashMap在进行扩容时，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 <code>(n - 1) &amp; hash</code> 的结果相比，只是多了<strong>一个</strong> bit 位，所以节点要么就在<strong>原来的位置</strong>，要么就被分配到 “<strong>原位置+旧容量</strong>“ 这个位置。</li>
</ol>
<p>例如：16 扩展到32时</p>
<p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/16%E6%89%A9%E5%B1%95%E5%88%B032.png" srcset="/img/loading.gif" lazyload alt="16扩展到32"></p>
<p> 因此元素在重新计算hash之后，因为 n 变为 2 倍，那么 n-1 的标记范围在高位多<strong>1bit</strong>(<font color='red'>红色</font>)，因此新的 index 就会发生这样的变化： </p>
<p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/rehash%E5%90%8E%E7%9A%84index%E5%8F%98%E5%8C%96.png" srcset="/img/loading.gif" lazyload alt="rehash后的index变化"></p>
<ol start="3">
<li>两种情况会进行扩容：①元素个数超过「数组长度 * 负载因子」②桶链表长度大于 8 且 table 数组长度小于 64，则会进行扩容，而不是变成树结构</li>
</ol>
<h4 id="获取键值对的值-get-Object-key"><a href="#获取键值对的值-get-Object-key" class="headerlink" title="获取键值对的值 get(Object key)"></a>获取键值对的值 get(Object key)</h4><ul>
<li>核心方法是 <code>getNode(...)</code>，根据 <code>key</code> 找 <code>value</code> 并返回，找不到则返回 <code>null</code></li>
<li><code>key</code> 传入时需要 <code>hash(int)</code> 计算一次，因为 <code>put(K, V)</code> 时也用到 <code>hash(int)</code></li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">get</span><span class="hljs-params">(Object key)</span> </span>&#123;<br>    Node&lt;K,V&gt; e;<br>    <span class="hljs-keyword">return</span> (e = getNode(hash(key), key)) == <span class="hljs-keyword">null</span> ? <span class="hljs-keyword">null</span> : e.value;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="Map-get-实现方法及相关方法-getNode-int-hash-Object-key"><a href="#Map-get-实现方法及相关方法-getNode-int-hash-Object-key" class="headerlink" title="Map.get 实现方法及相关方法 getNode(int hash, Object key)"></a>Map.get 实现方法及相关方法 getNode(int hash, Object key)</h4><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">final</span> Node&lt;K,V&gt; <span class="hljs-title">getNode</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, Object key)</span> </span>&#123;<br>    <span class="hljs-comment">// tab: 当前 hashmap 的散列表</span><br>    <span class="hljs-comment">// first: 桶中的首节点</span><br>    <span class="hljs-comment">// e: 临时节点</span><br>	<span class="hljs-comment">// n: table 数组长度</span><br>    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; <span class="hljs-keyword">int</span> n; K k;<br>    <span class="hljs-comment">// 给 tab, n, first 初始化赋值，并判空</span><br>    <span class="hljs-keyword">if</span> ((tab = table) != <span class="hljs-keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="hljs-number">0</span> &amp;&amp;<br>        (first = tab[(n - <span class="hljs-number">1</span>) &amp; hash]) != <span class="hljs-keyword">null</span>) &#123;<br>        <span class="hljs-comment">// (key != null &amp;&amp; key.equals(k)) 正好头结点就是需要找的节点</span><br>        <span class="hljs-keyword">if</span> (first.hash == hash &amp;&amp; <span class="hljs-comment">// always check first node</span><br>            ((k = first.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))<br>            <span class="hljs-keyword">return</span> first;<br>        <span class="hljs-comment">// 当前桶是链表或红黑树</span><br>        <span class="hljs-keyword">if</span> ((e = first.next) != <span class="hljs-keyword">null</span>) &#123;<br>            <span class="hljs-comment">// 桶升级成红黑树</span><br>            <span class="hljs-keyword">if</span> (first <span class="hljs-keyword">instanceof</span> TreeNode)<br>                <span class="hljs-keyword">return</span> ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);<br>            <span class="hljs-comment">// 桶结构为链表</span><br>            <span class="hljs-keyword">do</span> &#123;<br>                <span class="hljs-comment">// 循环查找</span><br>                <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp;<br>                    ((k = e.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))<br>                    <span class="hljs-keyword">return</span> e;<br>            &#125; <span class="hljs-keyword">while</span> ((e = e.next) != <span class="hljs-keyword">null</span>);<br>        &#125;<br>    &#125;<br>    <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="删除-remove"><a href="#删除-remove" class="headerlink" title="删除 remove"></a>删除 remove</h4><ul>
<li>实现方法为 <code>removeNode(...)</code> <ul>
<li><code>removeNode(int hash, Object key, Object value, boolean matchValue boolean movable)</code></li>
<li><code>matchValue == false</code> 表示必须是 <code>key &amp; value</code> 都相同才删除</li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">remove</span><span class="hljs-params">(Object key)</span> </span>&#123;<br>    Node&lt;K,V&gt; e;<br>    <span class="hljs-keyword">return</span> (e = removeNode(hash(key), key, <span class="hljs-keyword">null</span>, <span class="hljs-keyword">false</span>, <span class="hljs-keyword">true</span>)) == <span class="hljs-keyword">null</span> ?<br>        <span class="hljs-keyword">null</span> : e.value;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li><code>key &amp; value</code> 都相同才能删除节点<ul>
<li><code>matchValue == true</code></li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">remove</span><span class="hljs-params">(Object key, Object value)</span> </span>&#123;<br>    <span class="hljs-keyword">return</span> removeNode(hash(key), key, value, <span class="hljs-keyword">true</span>, <span class="hljs-keyword">true</span>) != <span class="hljs-keyword">null</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="Map-remove-实现方法及相关方法-removeNode-…"><a href="#Map-remove-实现方法及相关方法-removeNode-…" class="headerlink" title="Map.remove 实现方法及相关方法 removeNode(…)"></a>Map.remove 实现方法及相关方法 removeNode(…)</h4><ul>
<li><code>matchValue</code>： <strong>true</strong>: <code>key &amp; value</code> 都相同才能删除；<strong>false</strong>: <code>key</code> 相同就可删除</li>
<li><code>movable</code>： <strong>false</strong>: 删除过程中不移动其他节点 </li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">final</span> Node&lt;K,V&gt; <span class="hljs-title">removeNode</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, Object key, Object value,</span></span><br><span class="hljs-function"><span class="hljs-params">                           <span class="hljs-keyword">boolean</span> matchValue, <span class="hljs-keyword">boolean</span> movable)</span> </span>&#123;<br>    <span class="hljs-comment">// tab: 引用 hashmap 中的散列表</span><br>    <span class="hljs-comment">// p: 当前 node 节点</span><br>    <span class="hljs-comment">// n: table散列表的数组长度</span><br>    <span class="hljs-comment">// index: 寻址结果</span><br>    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; <span class="hljs-keyword">int</span> n, index;<br>    <span class="hljs-comment">// 对变量初始化赋值，判空</span><br>    <span class="hljs-keyword">if</span> ((tab = table) != <span class="hljs-keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="hljs-number">0</span> &amp;&amp;<br>        (p = tab[index = (n - <span class="hljs-number">1</span>) &amp; hash]) != <span class="hljs-keyword">null</span>) &#123;<br>        <span class="hljs-comment">// node: 查找到的结果</span><br>        <span class="hljs-comment">// e: 当前node的下一个节点</span><br>        Node&lt;K,V&gt; node = <span class="hljs-keyword">null</span>, e; K k; V v;<br>        <span class="hljs-comment">// 当前桶中元素就是待删除元素</span><br>        <span class="hljs-keyword">if</span> (p.hash == hash &amp;&amp;<br>            ((k = p.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))<br>            node = p;<br>        <span class="hljs-comment">// 桶中遍历其他元素进行删除</span><br>        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((e = p.next) != <span class="hljs-keyword">null</span>) &#123;<br>            <span class="hljs-comment">// 桶为树结构</span><br>            <span class="hljs-keyword">if</span> (p <span class="hljs-keyword">instanceof</span> TreeNode)<br>                <span class="hljs-comment">// 树中查找</span><br>                node = ((TreeNode&lt;K,V&gt;)p).getTreeNode(hash, key);<br>            <span class="hljs-comment">// 桶为链表结构</span><br>            <span class="hljs-keyword">else</span> &#123;<br>                <span class="hljs-keyword">do</span> &#123;<br>                    <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp;<br>                        ((k = e.key) == key ||<br>                         (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k)))) &#123;<br>                        node = e;<br>                        <span class="hljs-keyword">break</span>;<br>                    &#125;<br>                    p = e;<br>                &#125; <span class="hljs-keyword">while</span> ((e = e.next) != <span class="hljs-keyword">null</span>);<br>            &#125;<br>        &#125;<br>        <br>        <span class="hljs-comment">// matchValue为false，就不进行后面的value值判断</span><br>        <span class="hljs-comment">// 为true，则找到value也匹配的情况</span><br>        <span class="hljs-keyword">if</span> (node != <span class="hljs-keyword">null</span> &amp;&amp; (!matchValue || (v = node.value) == value ||<br>                             (value != <span class="hljs-keyword">null</span> &amp;&amp; value.equals(v)))) &#123;<br>            <span class="hljs-comment">// 树节点删除</span><br>            <span class="hljs-keyword">if</span> (node <span class="hljs-keyword">instanceof</span> TreeNode)<br>                ((TreeNode&lt;K,V&gt;)node).removeTreeNode(<span class="hljs-keyword">this</span>, tab, movable);<br>            <span class="hljs-comment">// 上面的 if 的情况，桶中的首元素为待删除元素</span><br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (node == p)<br>                tab[index] = node.next;<br>            <span class="hljs-comment">// 链表结构删除节点</span><br>            <span class="hljs-keyword">else</span><br>                p.next = node.next;<br>            ++modCount;<br>            --size;<br>            <span class="hljs-comment">// 在HashMap中是空方法，为了给其子类LinkedHashMap继承重写</span><br>            afterNodeRemoval(node);<br>            <span class="hljs-keyword">return</span> node;<br>        &#125;<br>    &#125;<br>    <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="获取-get-Object-key"><a href="#获取-get-Object-key" class="headerlink" title="获取 get(Object key)"></a>获取 get(Object key)</h4><ul>
<li>实现方法 <code>getNode(...)</code>，找不到，则返回 <code>null</code></li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">get</span><span class="hljs-params">(Object key)</span> </span>&#123;<br>    Node&lt;K,V&gt; e;<br>    <span class="hljs-keyword">return</span> (e = getNode(hash(key), key)) == <span class="hljs-keyword">null</span> ? <span class="hljs-keyword">null</span> : e.value;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="Map-get-的实现方法及其相关方法"><a href="#Map-get-的实现方法及其相关方法" class="headerlink" title="Map.get 的实现方法及其相关方法"></a>Map.get 的实现方法及其相关方法</h4><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">final</span> Node&lt;K,V&gt; <span class="hljs-title">getNode</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, Object key)</span> </span>&#123;<br>    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; <span class="hljs-keyword">int</span> n; K k;<br>    <span class="hljs-comment">// 对成员变量赋值，并判空</span><br>    <span class="hljs-keyword">if</span> ((tab = table) != <span class="hljs-keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="hljs-number">0</span> &amp;&amp;<br>        (first = tab[(n - <span class="hljs-number">1</span>) &amp; hash]) != <span class="hljs-keyword">null</span>) &#123;<br>        <span class="hljs-comment">// 如果桶顶元素符合key，则直接返回</span><br>        <span class="hljs-keyword">if</span> (first.hash == hash &amp;&amp; <span class="hljs-comment">// always check first node</span><br>            ((k = first.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))<br>            <span class="hljs-keyword">return</span> first;<br>        <span class="hljs-comment">// 桶后面有其他元素碰撞</span><br>        <span class="hljs-keyword">if</span> ((e = first.next) != <span class="hljs-keyword">null</span>) &#123;<br>            <span class="hljs-comment">// 红黑树结构，二分查找，O(logn)</span><br>            <span class="hljs-keyword">if</span> (first <span class="hljs-keyword">instanceof</span> TreeNode)<br>                <span class="hljs-keyword">return</span> ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);<br>            <span class="hljs-comment">// 链表</span><br>            <span class="hljs-keyword">do</span> &#123;<br>                <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp;<br>                    ((k = e.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))<br>                    <span class="hljs-keyword">return</span> e;<br>            &#125; <span class="hljs-keyword">while</span> ((e = e.next) != <span class="hljs-keyword">null</span>);<br>        &#125;<br>    &#125;<br>    <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="hash-计算"><a href="#hash-计算" class="headerlink" title="hash 计算"></a>hash 计算</h4><ul>
<li>再次计算 <code>key.hashCode()</code>，将 <strong>高 16 位</strong> 参与进来，使得哈希值<strong>更加分散</strong></li>
<li><code>(h = key.hashCode()) ^ (h &gt;&gt;&gt; 16)</code></li>
<li>右移 16 位， 与原先的哈希值<strong>异或</strong></li>
<li>将 高 16 位 与原哈希值异或，即将高 16 位 参与进哈希值的运算中。随着元素的增加，哈希碰撞的几率会更低。</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> <span class="hljs-title">hash</span><span class="hljs-params">(Object key)</span> </span>&#123;<br>    <span class="hljs-keyword">int</span> h;<br>    <span class="hljs-keyword">return</span> (key == <span class="hljs-keyword">null</span>) ? <span class="hljs-number">0</span> : (h = key.hashCode()) ^ (h &gt;&gt;&gt; <span class="hljs-number">16</span>);<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="计算大于等于给定数的最近2次幂数"><a href="#计算大于等于给定数的最近2次幂数" class="headerlink" title="计算大于等于给定数的最近2次幂数"></a>计算大于等于给定数的最近2次幂数</h4><p>输入7，结果为8；输入10，结果为16；</p>
<p>🌰：以入参为 10 为例</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> <span class="hljs-title">tableSizeFor</span><span class="hljs-params">(<span class="hljs-keyword">int</span> cap)</span> </span>&#123;<br>    <span class="hljs-keyword">int</span> n = cap - <span class="hljs-number">1</span>; <span class="hljs-comment">// 9</span><br>    n |= n &gt;&gt;&gt; <span class="hljs-number">1</span>; <span class="hljs-comment">// 0b1001 | 0b0100 = 0b1101</span><br>    n |= n &gt;&gt;&gt; <span class="hljs-number">2</span>; <span class="hljs-comment">// 0b1101 | 0b0011 = 0b1111</span><br>    n |= n &gt;&gt;&gt; <span class="hljs-number">4</span>; <span class="hljs-comment">// 下面都是 0b1111</span><br>    n |= n &gt;&gt;&gt; <span class="hljs-number">8</span>;<br>    n |= n &gt;&gt;&gt; <span class="hljs-number">16</span>;<br>    <span class="hljs-comment">// n = 0b1111</span><br>    <span class="hljs-comment">// (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1</span><br>    <span class="hljs-comment">// n + 1 = 15 + 1 = 16</span><br>    <span class="hljs-keyword">return</span> (n &lt; <span class="hljs-number">0</span>) ? <span class="hljs-number">1</span> : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + <span class="hljs-number">1</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<p>📌注：如果一开始 <code>n</code> 不减一，算出来的结果会大一倍</p>
<h3 id="Ⅳ、HashMap-初始化建议"><a href="#Ⅳ、HashMap-初始化建议" class="headerlink" title="Ⅳ、HashMap 初始化建议"></a>Ⅳ、HashMap 初始化建议</h3><h4 id="一、初始化问题"><a href="#一、初始化问题" class="headerlink" title="一、初始化问题"></a>一、初始化问题</h4><p>由于 HashMap 自动扩容机制，需要重新计算键值对的哈希值，并进行拷贝，开销较大，为了避免自动扩容，尽量在创建哈希表时，<strong>有参构造</strong> 指定初始容量。</p>
<p>HashMap 的扩容机制 在 <code>resize()</code> 有介绍，两种情况会进行扩容：①元素个数超过「数组长度 * 负载因子」（threshold = loadFactor * capacity）②桶链表长度大于 8 且 table 数组长度小于 64，则会进行<strong>扩容</strong>，而不是变成树结构</p>
<h4 id="二、建议初始化大小计算"><a href="#二、建议初始化大小计算" class="headerlink" title="二、建议初始化大小计算"></a>二、建议初始化大小计算</h4><ul>
<li>根据《阿里巴巴Java开发手册》编程规约中，对集合处理有以下建议：</li>
</ul>
<p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/HashMap%E5%88%9D%E5%A7%8B%E5%8C%96%E5%88%9B%E5%BB%BA%E6%8C%87%E5%AE%9A%E5%A4%A7%E5%B0%8F.png" srcset="/img/loading.gif" lazyload alt="HashMap创建指定初始化大小"></p>
<p>🌰举例：</p>
<p>如果设置的默认值为 7，经过 <code>tableSizeFor()</code> 计算后，设置为 8。此时 <code>Threshold = 8 * 0.75 = 6</code>，会进行一次扩容，并不是最佳方案。</p>
<p>通过 <code>initialCapacity / 0.75F + 1.0F</code> 计算，得到设置值为 <code>7 / 0.75 + 1 = 10</code>，经过 <code>tableSizeFor()</code> 计算后设置为 16，在容量达到 <code>16 * 0.75 = 12</code> 时进行扩容，符合预期。</p>
<h3 id="Ⅴ、线程安全问题"><a href="#Ⅴ、线程安全问题" class="headerlink" title="Ⅴ、线程安全问题"></a>Ⅴ、线程安全问题</h3><h4 id="一、HashMap-线程安全问题"><a href="#一、HashMap-线程安全问题" class="headerlink" title="一、HashMap 线程安全问题"></a>一、HashMap 线程安全问题</h4><p>HashMap的线程不安全体现在会造成<strong>死循环</strong>、<strong>数据丢失</strong>、<strong>数据覆盖</strong>这些问题。其中死循环和数据丢失是在 <code>JDK1.7</code>   中出现的问题，在 <code>JDK1.8</code> 中已经得到解决，然而 1.8 中仍会有<strong>数据覆盖</strong>的问题，即在并发执行 <code>HashMap::put</code> 操作时会发生数据覆盖的情况。</p>
<h4 id="二、JDK7-HashMap并发死链问题"><a href="#二、JDK7-HashMap并发死链问题" class="headerlink" title="二、JDK7 HashMap并发死链问题"></a>二、JDK7 HashMap并发死链问题</h4><ul>
<li>首先说明：<code>JDK7</code> 中 <code>HashMap</code> 插入操作是 <strong>头插法</strong>。</li>
</ul>
<p>关注到 <code>JDK7</code> 的扩容操作，实现的方法是 <code>transfer(...)</code></p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">transfer</span><span class="hljs-params">(Entry[] newTable, <span class="hljs-keyword">boolean</span> rehash)</span> </span>&#123;<br>    <span class="hljs-keyword">int</span> newCapacity = newTable.length;<br>    <span class="hljs-keyword">for</span> (Entry&lt;K,V&gt; e : table) &#123;<br>        <span class="hljs-keyword">while</span>(<span class="hljs-keyword">null</span> != e) &#123;<br>            Entry&lt;K,V&gt; next = e.next; <span class="hljs-comment">// ①</span><br>            <span class="hljs-keyword">if</span> (rehash) &#123;<br>                e.hash = <span class="hljs-keyword">null</span> == e.key ? <span class="hljs-number">0</span> : hash(e.key);<br>            &#125;<br>            <span class="hljs-keyword">int</span> i = indexFor(e.hash, newCapacity); <br>            e.next = newTable[i]; <span class="hljs-comment">// ②</span><br>            newTable[i] = e; <span class="hljs-comment">// ③</span><br>            e = next; <span class="hljs-comment">// ④</span><br>        &#125;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<p>①：<code>Entry&lt;K,V&gt; next = e.next;</code> 获取 e 的下一个节点指针</p>
<p>②：<code>e.next = newTable[i];</code> 待转移节点指向新桶</p>
<p>③：<code>newTable[i] = e;</code> 待转移节点移动到桶位置</p>
<p>④：<code>e = next;</code> 成功移动后，将 e 指针回到原来链表位置，对下一个节点转移\</p>
<p>以下视频有详细讲解：</p>
<blockquote>
<p><a target="_blank" rel="noopener" href="https://www.bilibili.com/video/BV1n541177Ea">https://www.bilibili.com/video/BV1n541177Ea</a></p>
<p><a target="_blank" rel="noopener" href="https://coolshell.cn/articles/9606.html#">https://coolshell.cn/articles/9606.html#</a></p>
</blockquote>
<h2 id="三、HashSet"><a href="#三、HashSet" class="headerlink" title="三、HashSet"></a>三、HashSet</h2><ul>
<li>基于 <code>HashCode</code> 实现元素不重复</li>
<li>当存入元素哈希码相同时，调用 <code>equals</code> 确认，若为 <code>true</code>，拒绝后者存入「实现不重复」</li>
</ul>
<h3 id="Ⅰ、Field-1"><a href="#Ⅰ、Field-1" class="headerlink" title="Ⅰ、Field"></a>Ⅰ、Field</h3><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// HashSet 底层使用 HashMap 实现</span><br><span class="hljs-keyword">private</span> <span class="hljs-keyword">transient</span> HashMap&lt;E,Object&gt; map;<br><span class="hljs-comment">// 虚拟对象，充当 map 的 value</span><br><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> Object PRESENT = <span class="hljs-keyword">new</span> Object();<br></code></pre></div></td></tr></table></figure>


<h3 id="Ⅱ、Constructor-1"><a href="#Ⅱ、Constructor-1" class="headerlink" title="Ⅱ、Constructor"></a>Ⅱ、Constructor</h3><h4 id="无参构造-1"><a href="#无参构造-1" class="headerlink" title="无参构造"></a>无参构造</h4><ul>
<li>构造一个新的空集合；备份HashMap实例具有默认的初始容量（<strong>16</strong>）和负载因子（<strong>0.75</strong>）</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">HashSet</span><span class="hljs-params">()</span> </span>&#123;<br>    map = <span class="hljs-keyword">new</span> HashMap&lt;&gt;();<br>&#125;<br></code></pre></div></td></tr></table></figure>








<h2 id="四、TreeSet"><a href="#四、TreeSet" class="headerlink" title="四、TreeSet"></a>四、TreeSet</h2><ul>
<li>基于排列顺序实现元素不重复</li>
<li>实现 <code>SortedSet</code> 接口，对集合元素自动排序</li>
<li>元素对象的类型<strong>必须</strong>实现 <code>Comparable</code> 接口，指定排序规则</li>
<li>通过 <code>CompareTo</code> 方法确定是否为<strong>重复元素</strong></li>
</ul>
<h2 id="五、PriorityQueue"><a href="#五、PriorityQueue" class="headerlink" title="五、PriorityQueue"></a>五、PriorityQueue</h2><ul>
<li>看名称知道，该类属于 <code>Queue </code>，由默认的排序器维护的堆为 **小根堆 **</li>
<li><strong>优先队列</strong> 是 Java 实现 <strong>堆</strong> 的方式</li>
<li><strong>堆</strong> 逻辑上是<strong>完全二叉树</strong>，按照<strong>层序遍历</strong>的顺序，可以使用<strong>数组</strong>进行存储，而其余的树大多是用链式数据结构存储。</li>
<li>堆分类：<ul>
<li><strong>大根堆</strong>：根节点「整棵树或任意子树」，父节点的值最大</li>
<li><strong>小根堆</strong>：同上，父节点值最小</li>
</ul>
</li>
<li>堆的操作：<ul>
<li><strong>上浮</strong>：向堆<strong>添加</strong>新元素后的堆平衡操作</li>
<li><strong>下沉</strong>：取出堆顶并将<strong>堆尾</strong>换至堆顶后的堆平衡操作</li>
</ul>
</li>
</ul>
<p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/%E5%B0%8F%E9%A1%B6%E5%A0%86.png" srcset="/img/loading.gif" lazyload alt="小根堆"></p>
<p>根据完全二叉树的性质，节点元素的下标与其父节点、左孩子和右孩子的关系：<br>$$<br>leftChild = parent \times 2 + 1<br>$$</p>
<p>$$<br>rightChild = parent \times 2 + 2<br>$$</p>
<p>$$<br>parent = (child - 1) / 2<br>$$</p>
<p>时间复杂度</p>
<ul>
<li><code>peek()</code> &amp; <code>element()</code> -&gt; <strong>O(1)</strong></li>
<li><code>add()</code> &amp; <code>offer()</code> &amp; <code>remove()</code> &amp; <code>poll()</code> -&gt; <strong>O(logN)</strong></li>
<li>建堆 -&gt; <strong>O(n)</strong></li>
<li>堆排序：把根与末尾 n 调换，堆化，再把 n - 1 与根调换，最终为倒序「小根堆」<ul>
<li>log n + log (n - 1) + … + 1 = <strong>O(nlogn)</strong></li>
<li>空间 **O(1)**，只需要交换的临时变量，原来的堆空间「数组」基础上做交换即可</li>
</ul>
</li>
</ul>
<h3 id="Ⅰ、Field-2"><a href="#Ⅰ、Field-2" class="headerlink" title="Ⅰ、Field"></a>Ⅰ、Field</h3><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-comment">// 默认初始化大小</span><br><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> DEFAULT_INITIAL_CAPACITY = <span class="hljs-number">11</span>; <br><span class="hljs-comment">// 优先队列存储数据结构为数组，不能参与序列化</span><br><span class="hljs-keyword">transient</span> Object[] queue;<br><span class="hljs-comment">// 堆中元素数量</span><br><span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> size = <span class="hljs-number">0</span>;<br><span class="hljs-comment">// 造成堆结构变化的次数「插入、删除、交换」</span><br><span class="hljs-keyword">transient</span> <span class="hljs-keyword">int</span> modCount = <span class="hljs-number">0</span>;<br><span class="hljs-comment">// 构造器、默认为小根堆，可在有参中自定义</span><br><span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> Comparator&lt;? <span class="hljs-keyword">super</span> E&gt; comparator;<br></code></pre></div></td></tr></table></figure>
<h3 id="Ⅱ、Constructor-2"><a href="#Ⅱ、Constructor-2" class="headerlink" title="Ⅱ、Constructor"></a>Ⅱ、Constructor</h3><h4 id="无参构造-2"><a href="#无参构造-2" class="headerlink" title="无参构造"></a>无参构造</h4><ul>
<li>使用默认初始化大小「<strong>11</strong>」创建数组，默认排序器「<strong>小根堆</strong>」</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">PriorityQueue</span><span class="hljs-params">()</span> </span>&#123;<br>    <span class="hljs-keyword">this</span>(DEFAULT_INITIAL_CAPACITY, <span class="hljs-keyword">null</span>);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<h4 id="有参构造-1"><a href="#有参构造-1" class="headerlink" title="有参构造"></a>有参构造</h4><ul>
<li>指定初始化容量 和 自定义构造器</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">PriorityQueue</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity,</span></span><br><span class="hljs-function"><span class="hljs-params">                     Comparator&lt;? <span class="hljs-keyword">super</span> E&gt; comparator)</span> </span>&#123;<br>    <span class="hljs-comment">// Note: This restriction of at least one is not actually needed,</span><br>    <span class="hljs-comment">// but continues for 1.5 compatibility </span><br>    <span class="hljs-keyword">if</span> (initialCapacity &lt; <span class="hljs-number">1</span>) <span class="hljs-comment">// 对 1.5 以下版本向下兼容</span><br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException();<br>    <span class="hljs-keyword">this</span>.queue = <span class="hljs-keyword">new</span> Object[initialCapacity];<br>    <span class="hljs-keyword">this</span>.comparator = comparator;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>指定构造器，使用默认初始化容量「<strong>11</strong>」</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">PriorityQueue</span><span class="hljs-params">(Comparator&lt;? <span class="hljs-keyword">super</span> E&gt; comparator)</span> </span>&#123;<br>    <span class="hljs-keyword">this</span>(DEFAULT_INITIAL_CAPACITY, comparator);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>传入集合类，判断是不是 <code>SortedSet</code> 或 <code>PriorityQueue</code> ，是他们的实例，则会按照之前的顺序构造新的优先队列，否则按照默认排序器构造堆</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">PriorityQueue</span><span class="hljs-params">(Collection&lt;? extends E&gt; c)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (c <span class="hljs-keyword">instanceof</span> SortedSet&lt;?&gt;) &#123;<br>        SortedSet&lt;? extends E&gt; ss = (SortedSet&lt;? extends E&gt;) c;<br>        <span class="hljs-keyword">this</span>.comparator = (Comparator&lt;? <span class="hljs-keyword">super</span> E&gt;) ss.comparator();<br>        initElementsFromCollection(ss);<br>    &#125;<br>    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (c <span class="hljs-keyword">instanceof</span> PriorityQueue&lt;?&gt;) &#123;<br>        PriorityQueue&lt;? extends E&gt; pq = (PriorityQueue&lt;? extends E&gt;) c;<br>        <span class="hljs-keyword">this</span>.comparator = (Comparator&lt;? <span class="hljs-keyword">super</span> E&gt;) pq.comparator();<br>        initFromPriorityQueue(pq);<br>    &#125;<br>    <span class="hljs-keyword">else</span> &#123;<br>        <span class="hljs-keyword">this</span>.comparator = <span class="hljs-keyword">null</span>;<br>        initFromCollection(c);<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h3 id="Ⅲ、Method-1"><a href="#Ⅲ、Method-1" class="headerlink" title="Ⅲ、Method"></a>Ⅲ、Method</h3><h4 id="插入元素-add-E-e-amp-offer-E-e"><a href="#插入元素-add-E-e-amp-offer-E-e" class="headerlink" title="插入元素 add(E e) &amp; offer(E e)"></a>插入元素 add(E e) &amp; offer(E e)</h4><figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">add</span><span class="hljs-params">(E e)</span> </span>&#123;<br>    <span class="hljs-keyword">return</span> offer(e);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">offer</span><span class="hljs-params">(E e)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (e == <span class="hljs-keyword">null</span>)<br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> NullPointerException();<br>    modCount++;<br>    <span class="hljs-keyword">int</span> i = size; <span class="hljs-comment">// 获取堆数组的容量</span><br>    <span class="hljs-keyword">if</span> (i &gt;= queue.length)<br>        grow(i + <span class="hljs-number">1</span>); <span class="hljs-comment">// 扩容</span><br>    size = i + <span class="hljs-number">1</span>; <span class="hljs-comment">// 让 size 到下一个位置，准备插入元素</span><br>    <span class="hljs-keyword">if</span> (i == <span class="hljs-number">0</span>) <span class="hljs-comment">// 数组为空，直接插入</span><br>        queue[<span class="hljs-number">0</span>] = e;<br>    <span class="hljs-keyword">else</span><br>        siftUp(i, e); <span class="hljs-comment">// 插入到末尾，然后向上浮动调整</span><br>    <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li><code>add()</code> 直接调 <code>offer()</code></li>
<li>插入元素之前需要判断数组容量够不够，调用 <code>grow()</code> 扩容</li>
<li>插入元素可能会破坏原堆的性质，所以插入到数组末尾，然后再让末尾元素递归上浮「<code>siftUp</code>」调整</li>
</ul>
<h4 id="扩容函数-grow"><a href="#扩容函数-grow" class="headerlink" title="扩容函数 grow()"></a>扩容函数 grow()</h4><ul>
<li>本质是数组的拷贝 <code>Arrays.copyOf(oldArray, newArray)</code></li>
<li><strong>oldCap &lt; 64</strong>：<code>newCap = oldCap x 2 + 2</code></li>
<li><strong>oldCap &gt;= 64</strong>：<code>newCap = oldCap x 2</code></li>
<li><strong>oldCap &gt; Integer.MAX_VALUE - 8</strong>：<code>newCap = oldCap x 2 + 2</code></li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">grow</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;<br>    <span class="hljs-keyword">int</span> oldCapacity = queue.length;<br>    <span class="hljs-comment">// Double size if small; else grow by 50%</span><br>    <span class="hljs-keyword">int</span> newCapacity = oldCapacity + ((oldCapacity &lt; <span class="hljs-number">64</span>) ?<br>                                     (oldCapacity + <span class="hljs-number">2</span>) :<br>                                     (oldCapacity &gt;&gt; <span class="hljs-number">1</span>));<br>    <span class="hljs-comment">// overflow-conscious code</span><br>    <span class="hljs-keyword">if</span> (newCapacity - MAX_ARRAY_SIZE &gt; <span class="hljs-number">0</span>)<br>        newCapacity = hugeCapacity(minCapacity);<br>    queue = Arrays.copyOf(queue, newCapacity);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>添加元素传进来的 <code>minCapacity = i + 1</code>，即原数组的容量 + 1，该值含义是 扩容后至少达到指定容量</li>
<li>小于 0，说明溢出，抛异常</li>
<li>如果指定容量比安全数组大小 <code>MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8</code> 大，最多给到 <code>Integer.MAX_VALUE</code> ，否则只给到 <code>MAX_ARRAY_SIZE </code></li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> <span class="hljs-title">hugeCapacity</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (minCapacity &lt; <span class="hljs-number">0</span>) <span class="hljs-comment">// overflow</span><br>        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> OutOfMemoryError();<br>    <span class="hljs-keyword">return</span> (minCapacity &gt; MAX_ARRAY_SIZE) ?<br>        Integer.MAX_VALUE :<br>        MAX_ARRAY_SIZE;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="末尾元素上浮，调整堆化-siftUp-int-k-E-x"><a href="#末尾元素上浮，调整堆化-siftUp-int-k-E-x" class="headerlink" title="末尾元素上浮，调整堆化 siftUp(int k, E x)"></a>末尾元素上浮，调整堆化 siftUp(int k, E x)</h4><ul>
<li>先将新元素插入到数组的末尾，即完全二叉树的末尾叶子结点，然后按照排序器规则，与其根节点比较，判断是否交换，循环此过程，直到堆化。</li>
</ul>
<p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/PriorityQueue_siftUp.png" srcset="/img/loading.gif" lazyload alt="siftUp过程"></p>
<ul>
<li>判断是否自定义排序器规则，有就用自定义的，没有就默认构造成<strong>小根堆</strong></li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">siftUp</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k, E x)</span> </span>&#123;    <br>    <span class="hljs-keyword">if</span> (comparator != <span class="hljs-keyword">null</span>)        <br>        siftUpUsingComparator(k, x);    <br>    <span class="hljs-keyword">else</span>        <br>        siftUpComparable(k, x);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>自定义排序器<ul>
<li>先将插入元素强转成 <code>Comparable</code>，让后面的值比较 <code>compareTo</code> 正常进行</li>
<li>完全二叉树索引规则求父节点索引 <code>parent = (child - 1) / 2</code></li>
<li>满足自定义规则，break，插入到当前位置结束</li>
<li>不满足，父节点移到子节点处，下一次循环会重新计算此次父节点的父节点</li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">siftUpComparable</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k, E x)</span> </span>&#123;<br>    Comparable&lt;? <span class="hljs-keyword">super</span> E&gt; key = (Comparable&lt;? <span class="hljs-keyword">super</span> E&gt;) x;<br>    <span class="hljs-keyword">while</span> (k &gt; <span class="hljs-number">0</span>) &#123;<br>        <span class="hljs-keyword">int</span> parent = (k - <span class="hljs-number">1</span>) &gt;&gt;&gt; <span class="hljs-number">1</span>;<br>        Object e = queue[parent];<br>        <span class="hljs-keyword">if</span> (key.compareTo((E) e) &gt;= <span class="hljs-number">0</span>)<br>            <span class="hljs-keyword">break</span>;<br>        queue[k] = e;<br>        k = parent;<br>    &#125;<br>    queue[k] = key;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>默认排序器「<strong>小根堆</strong>」<ul>
<li>待插入元素 x <code>&gt;=</code> 父节点 e，break，就插入到当前位置</li>
<li>父节点比子节点小，所以堆是<strong>小根堆</strong></li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">siftUpUsingComparator</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k, E x)</span> </span>&#123;<br>    <span class="hljs-keyword">while</span> (k &gt; <span class="hljs-number">0</span>) &#123;<br>        <span class="hljs-keyword">int</span> parent = (k - <span class="hljs-number">1</span>) &gt;&gt;&gt; <span class="hljs-number">1</span>;<br>        Object e = queue[parent];<br>        <span class="hljs-keyword">if</span> (comparator.compare(x, (E) e) &gt;= <span class="hljs-number">0</span>)<br>            <span class="hljs-keyword">break</span>;<br>        queue[k] = e;<br>        k = parent;<br>    &#125;<br>    queue[k] = x;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="获取堆顶元素-element-amp-peek"><a href="#获取堆顶元素-element-amp-peek" class="headerlink" title="获取堆顶元素 element() &amp; peek()"></a>获取堆顶元素 element() &amp; peek()</h4><ul>
<li><code>element()</code> &amp; <code>peek()</code> 都获取堆顶元素，但不删除。前者获取不到抛异常，后者返回 null</li>
<li>返回下标为 0 的元素，大顶堆返回最大值，小顶堆返回最小值</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">peek</span><span class="hljs-params">()</span> </span>&#123;<br>    <span class="hljs-keyword">return</span> (size == <span class="hljs-number">0</span>) ? <span class="hljs-keyword">null</span> : (E) queue[<span class="hljs-number">0</span>];<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h4 id="删除元素-remove-amp-poll"><a href="#删除元素-remove-amp-poll" class="headerlink" title="删除元素 remove() &amp; poll()"></a>删除元素 remove() &amp; poll()</h4><ul>
<li><code>remove()</code> &amp; <code>poll()</code> 都删除堆顶元素，前者失败抛异常，后者失败返回 null</li>
<li>删除元素会改变堆结构，所以删除完后要调整，将末尾元素移到堆顶，然后下沉「<code>siftDown()</code>」</li>
<li><code>size</code> 判空，为空返回 null</li>
<li>获取 <code>size</code> 减一后的容量 <code>s</code></li>
<li>保存堆顶即为 <code>result</code> 最后返回</li>
<li>保存数组尾元素，然后将尾元素删掉「置为null」</li>
<li>下沉调整堆结构 「<code>siftDown()</code>」</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">poll</span><span class="hljs-params">()</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (size == <span class="hljs-number">0</span>)<br>        <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;<br>    <span class="hljs-keyword">int</span> s = --size;<br>    modCount++;<br>    E result = (E) queue[<span class="hljs-number">0</span>];<br>    E x = (E) queue[s];<br>    queue[s] = <span class="hljs-keyword">null</span>;<br>    <span class="hljs-keyword">if</span> (s != <span class="hljs-number">0</span>)<br>        siftDown(<span class="hljs-number">0</span>, x);<br>    <span class="hljs-keyword">return</span> result;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<h4 id="下沉-siftDown-int-k-E-x"><a href="#下沉-siftDown-int-k-E-x" class="headerlink" title="下沉 siftDown(int k, E x)"></a>下沉 siftDown(int k, E x)</h4><ul>
<li>把末尾元素放到堆顶，然后下沉</li>
</ul>
<p><img src="https://gitee.com/hypocrite30/ImgBed/raw/master/img/JavaCommons/PriorityQueue_siftDown.png" srcset="/img/loading.gif" lazyload alt="siftDown"></p>
<ul>
<li>判断使用自定义排序器「如果构造时指定有的话」还是默认排序器</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">siftDown</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k, E x)</span> </span>&#123;<br>    <span class="hljs-keyword">if</span> (comparator != <span class="hljs-keyword">null</span>)<br>        siftDownUsingComparator(k, x);<br>    <span class="hljs-keyword">else</span><br>        siftDownComparable(k, x);<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>使用自定义排序器</li>
<li>强转 <code>Comparable</code>，便于下面 <code>compareTo()</code> 正常使用</li>
<li><code>half</code> 为数组中间位置，游标 <code>k</code> 的循环范围只有数组一半，另一半不用动，因为下沉需要找到两个孩子较小或较大的一个进行交换即可</li>
<li>获取左孩子索引 <code>(parent / 2) + 1</code>，获取左孩子值 <code>c</code></li>
<li>获取右孩子索引 <code>leftChild + 1</code></li>
<li>取出符合排序器条件的孩子「left or right」，值保存为 <code>c</code></li>
<li>原堆末尾节点 <code>x</code> 与孩子值做判断，满足排序器，break，插入到当前位置「k」即可</li>
<li>否则与孩子进行交换 </li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">siftDownComparable</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k, E x)</span> </span>&#123;<br>    Comparable&lt;? <span class="hljs-keyword">super</span> E&gt; key = (Comparable&lt;? <span class="hljs-keyword">super</span> E&gt;)x;<br>    <span class="hljs-keyword">int</span> half = size &gt;&gt;&gt; <span class="hljs-number">1</span>;        <span class="hljs-comment">// loop while a non-leaf</span><br>    <span class="hljs-keyword">while</span> (k &lt; half) &#123;<br>        <span class="hljs-keyword">int</span> child = (k &lt;&lt; <span class="hljs-number">1</span>) + <span class="hljs-number">1</span>; <span class="hljs-comment">// assume left child is least</span><br>        Object c = queue[child];<br>        <span class="hljs-keyword">int</span> right = child + <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">if</span> (right &lt; size &amp;&amp;<br>            ((Comparable&lt;? <span class="hljs-keyword">super</span> E&gt;) c).compareTo((E) queue[right]) &gt; <span class="hljs-number">0</span>)<br>            c = queue[child = right];<br>        <span class="hljs-keyword">if</span> (key.compareTo((E) c) &lt;= <span class="hljs-number">0</span>)<br>            <span class="hljs-keyword">break</span>;<br>        queue[k] = c;<br>        k = child;<br>    &#125;<br>    queue[k] = key;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<ul>
<li>使用默认排序器</li>
<li>前面同上</li>
<li>默认排序器选择较小的孩子，值保存为 <code>c</code></li>
<li>后面同上</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">siftDownUsingComparator</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k, E x)</span> </span>&#123;<br>    <span class="hljs-keyword">int</span> half = size &gt;&gt;&gt; <span class="hljs-number">1</span>;<br>    <span class="hljs-keyword">while</span> (k &lt; half) &#123;<br>        <span class="hljs-keyword">int</span> child = (k &lt;&lt; <span class="hljs-number">1</span>) + <span class="hljs-number">1</span>;<br>        Object c = queue[child];<br>        <span class="hljs-keyword">int</span> right = child + <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">if</span> (right &lt; size &amp;&amp;<br>            comparator.compare((E) c, (E) queue[right]) &gt; <span class="hljs-number">0</span>)<br>            c = queue[child = right];<br>        <span class="hljs-keyword">if</span> (comparator.compare(x, (E) c) &lt;= <span class="hljs-number">0</span>)<br>            <span class="hljs-keyword">break</span>;<br>        queue[k] = c;<br>        k = child;<br>    &#125;<br>    queue[k] = x;<br>&#125;<br></code></pre></div></td></tr></table></figure>


<h2 id="🔗Reference"><a href="#🔗Reference" class="headerlink" title="🔗Reference"></a>🔗Reference</h2><blockquote>
<p><a target="_blank" rel="noopener" href="https://tech.meituan.com/2016/06/24/java-hashmap.html">https://tech.meituan.com/2016/06/24/java-hashmap.html</a></p>
<p><a target="_blank" rel="noopener" href="https://developer.aliyun.com/topic/java20">《阿里巴巴Java开发手册 v1.7.0嵩山版》</a></p>
<p><a target="_blank" rel="noopener" href="https://www.bilibili.com/video/BV1n541177Ea">HashMap死链问题</a></p>
<p><a target="_blank" rel="noopener" href="https://pdai.tech/md/java/collection/java-collection-PriorityQueue.html"> Collection - PriorityQueue源码解析</a></p>
</blockquote>

            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/JavaSE/">JavaSE</a>
                    
                  </div>
                
                
              </div>
              
                <p class="note note-warning">
                  
                    本博客所有文章除特别声明外，均采用 <a target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！
                  
                </p>
              
              
                <div class="post-prevnext">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2021/08/29/JavaSE/ConcurrentHashMap%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90JDK8/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">ConcurrentHashMap源码分析JDK8</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2021/08/10/JavaSE/Java%E5%B8%B8%E7%94%A8%E9%9B%86%E5%90%88%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90%20%E2%85%A0/">
                        <span class="hidden-mobile">Java常用集合源码分析 Ⅰ</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div class="toc-body" id="toc-body"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    

    
      <a id="scroll-top-button" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
    

    
  </main>

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     © 2019-2021 
  </div>
  
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


  

  
</footer>


  <!-- SCRIPTS -->
  
  <script  src="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js" ></script>
<script  src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.3/dist/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/img-lazyload.js" ></script>
  



  



  <script  src="https://cdn.jsdelivr.net/npm/tocbot@4.12.0/dist/tocbot.min.js" ></script>



  <script  src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js" ></script>



  <script  src="https://cdn.jsdelivr.net/npm/anchor-js@4.3.0/anchor.min.js" ></script>



  <script defer src="https://cdn.jsdelivr.net/npm/clipboard@2.0.6/dist/clipboard.min.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>




  <script  src="https://cdn.jsdelivr.net/npm/typed.js@2.0.11/lib/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var title = document.getElementById('subtitle').title;
      
      typing(title)
      
    })(window, document);
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    (function () {
      var path = "/local-search.xml";
      $('#local-search-input').on('click', function() {
        searchFunc(path, 'local-search-input', 'local-search-result');
      });
      $('#modalSearch').on('shown.bs.modal', function() {
        $('#local-search-input').focus();
      });
    })()
  </script>





  

  
    <!-- MathJax -->
    <script>
      MathJax = {
        tex: {
          inlineMath: [['$', '$'], ['\\(', '\\)']]
        },
        options: {
          renderActions: {
            findScript: [10, doc => {
              document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
                const display = !!node.type.match(/; *mode=display/);
                const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
                const text = document.createTextNode('');
                node.parentNode.replaceChild(text, node);
                math.start = { node: text, delim: '', n: 0 };
                math.end = { node: text, delim: '', n: 0 };
                doc.math.push(math);
              });
            }, '', false],
            insertedScript: [200, () => {
              document.querySelectorAll('mjx-container').forEach(node => {
                let target = node.parentNode;
                if (target.nodeName.toLowerCase() === 'li') {
                  target.parentNode.classList.add('has-jax');
                }
              });
            }, '', false]
          }
        }
      };
    </script>

    <script async src="https://cdn.jsdelivr.net/npm/mathjax@3.1.2/es5/tex-svg.js" ></script>

  











<!-- 主题的启动项 保持在最底部 -->
<script  src="/js/boot.js" ></script>


</body>
</html>
